package listbyorder.access001_100.test86;

import listbyorder.utils.ListNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/5 9:19
 */
public class Solution1 {

    // 方法一： 自己的想法
    // 定义两个指针，左右指针
    // 如果当前右指针的下一个节点大于等于X，则右指针右移，左指针不动
    // 如果当前右指针的下一个节点小于X，且当前左指针和右指针在同一个位置，则左右指针同时向右移动
    // 如果当前右指针的下一个节点小于X，则将R.next连接上R.next.next, 将L后面介绍R后面的元素
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode L = dummy;
        ListNode R = dummy;
        while (R.next != null) {
            if (R.next.val >= x) {
                R = R.next;
            } else {
                if (L.next == R.next) {
                    L = L.next;
                    R = R.next;
                }else{
                    ListNode next = L.next;
                    ListNode temp = R.next;
                    R.next = R.next.next;
                    L.next = temp;
                    temp.next = next;
                    L = L.next;
                }
            }
        }
        return dummy.next;
    }
}
